package Solution.problem081.SearchinRotatedSortedArray2;

import org.junit.Assert;
import org.junit.Test;

/**
 * @program Leetcode
 * @description:
 * Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
 *
 * (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
 *
 * You are given a target value to search. If found in the array return true, otherwise return false.
 *
 *题目大意：
 * 就是给你一个排序好的可能有重复值的数组，然后从某一个点旋转，变成一个新的数组
 * 然后给你一个值让你查找
 *
 * 思路：
 *  直接遍历肯定能得到答案，但是很明显不是让你这样做
 *  二分查找，然后注意边界选择～
 *
 * @author: lishangsheng
 * @create: 2019/06/15 12:48
 */
public class Solution {
    public Boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        return search(nums,start,end,target);

    }

    private boolean search(int[] nums,int start,int end,int target) {
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;

        /*中间的值大于目标值*/
        if (nums[mid] > target) {
            /*结尾小于中间值,证明最小点值在右边*/
            if (nums[end] < nums[mid]) {
                if (target < nums[end]) {
                    /*然后target小于右边界，证明目标值也在右边*/
                    return search(nums, mid + 1, end, target);
                } else if (target > nums[end]) {
                    /*结尾小于中间值,证明最小点值在右边，然后target大于右边界，证明目标值也在左边*/
                    return search(nums, start, mid - 1, target);
                } else {
                    return true;
                }
            } else if (nums[end] > nums[mid]) {
                /*右边界大于中间值，证明右边是递增的，最小值在左边*/
                return search(nums, start, mid - 1, target);
            } else {
                /*中间和右边界相等*/

                /*左边，中间，右边都相等，这个时候只能两边都查了*/
                return search(nums, start, mid - 1, target) || search(nums, mid + 1, end, target);

            }
        } else if (nums[mid] < target) {

            if (nums[end] > nums[mid]) {
                /*最小值在左边，右边是单调递增的*/
                if (nums[end] > target) {
                    /*目标值小于有边界，证明值在右边*/
                    return search(nums, mid + 1, end, target);
                } else if (nums[end] < target) {
                    /*目标值大于有边界，值可能在左边*/
                    return search(nums, start, mid - 1, target);
                } else {
                    return true;
                }
            } else if (nums[end] < nums[mid]) {
                return search(nums, mid + 1, end, target);

            } else {
                /*中间和右边界相等*/
                return search(nums, start, mid - 1, target) || search(nums, mid + 1, end, target);
            }
        } else {
            return true;
        }
    }


    @Test
    public void test() {
        int[] nums = new int[]{2, 5, 6, 0, 0, 1, 2};
        System.out.println(search(nums, 0).equals(true));
        System.out.println(search(nums, 3).equals(false));
        System.out.println(search(nums, 2).equals(true));
        System.out.println(search(nums, 6).equals(true));
        System.out.println(search(nums, 9).equals(false));
        System.out.println("-----------------------");

        int[] nums2 = new int[]{ 6,0, 0, 1, 2,3, 5, 6};
        System.out.println(search(nums2, 1).equals(true));
        System.out.println(search(nums2, 0).equals(true));
        System.out.println(search(nums2, 5).equals(true));
        System.out.println(search(nums2, 3).equals(true));
        System.out.println("-----------------------");
        int[] nums3 = new int[]{ 1};
        System.out.println(search(nums3, 1).equals(true));

        System.out.println("-----------------------");
        int[] nums4 = new int[]{ 3,5,1};
        System.out.println(search(nums4, 3).equals(true));

        System.out.println("-----------------------");

        int[] nums5 = new int[]{ 1,1,3,1};
        System.out.println(search(nums5, 3).equals(true));


        int[] nums6 = new int[]{ 1,1,3,1,1,1,1,1};
        System.out.println(search(nums6, 3).equals(true));

        int[] nums7 = new int[]{ 3,1,2,2,2};
        System.out.println(search(nums7, 1).equals(true));


    }
}
